/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-10-10
 * Time: 0:05
 */
public class BinarySearchTree {

    static class TreeNode {
         int key;
         TreeNode left;
         TreeNode right;

        public TreeNode(int key) {
            this.key = key;
        }
    }

    //二叉搜索树的根结点
    private TreeNode root;

    public void createTree() {
        TreeNode node1 = new TreeNode(76);
        TreeNode node2 = new TreeNode(54);
        TreeNode node3 = new TreeNode(89);
        TreeNode node4 = new TreeNode(44);
        TreeNode node5 = new TreeNode(65);
        TreeNode node6 = new TreeNode(90);

        node1.left = node2;
        node1.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.right = node6;

        root = node1;
    }

    public boolean find(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.key == key) {
                return true;
            }else if (cur.key < key) {
                cur = cur.right;
            }else {
                cur = cur.left;
            }
        }
        return false;
    }

    public boolean insert(int key) {
        //一开始树为空
        if (root == null) {
            TreeNode node = new TreeNode(key);
            root = node;
            return true;
        }

        //一开始树不为空
        TreeNode cur = root;  //遍历结点
        TreeNode parent = null; //插入位置的前一个结点

        while (cur != null) {
            //当树存在和新结点的值相同的结点
            if (cur.key == key) {
                return false;
            }

            //找插入位置
            if (key > cur.key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }

        //找到插入位置后
        TreeNode node = new TreeNode(key);
        if (key > parent.key) {
            parent.right = node;
            return true;
        }else {
            parent.left = node;
            return true;
        }
    }

    public boolean remove(int key) {
        //如果树为空树
        if (root == null) {
            return false;
        }

        //树不为空的情况
        TreeNode cur = root;
        TreeNode parent = null;
        //去找待删除结点
        while (cur != null) {
            if (cur.key == key) {
                break;
            }else if (key > cur.key) {
                parent = cur;
                cur = cur.right;
            }else {
                parent = cur;
                cur = cur.left;
            }
        }

        //如果cur == null，说明这棵树没有要删除的结点
        if (cur == null) {
            return false;
        }

        //找到待删除结点后
        if (cur.left == null && cur.right == null) {
            if (cur == root) {
                root = null;
            }else if (parent.left == cur) {
                parent.left = null;
            }else {
                parent.right = null;
            }
            return true;
        }else if (cur.left != null && cur.right == null) {
            if (cur == root) {
                root = cur.left;
            }else if (parent.left == cur) {
                parent.left = cur.left;
            }else {
                parent.right = cur.left;
            }
            return true;
        }else if (cur.left == null && cur.right != null) {
            if (cur == root) {
                root = cur.right;
            }else if (parent.left == cur) {
                parent.left = cur.right;
            }else {
                parent.right = cur.right;
            }
            return true;
        }else {
            TreeNode t = cur.right;  //用来找替换值的结点
            TreeNode tp = null;      //t的父结点

            //这里去找cur右子树的最小值
            while (t.left != null) {
                tp = t;
                t = t.left;
            }

            //找到后，替换cur的值
            cur.key = t.key;

            //处理t

            //防止t一开始就是最小值，而tp = null而引发的空指针异常
            if (t == cur.right) {
                if (t.right == null) {
                    cur.right = null;
                }else {
                    cur.right = t.right;
                }
            }else {
                if (t.right == null) {
                    tp.left = null;
                }else {
                    tp.left = t.right;
                }
            }
            return true;
        }
    }
}
